#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//链表结点
typedef struct LinkNode {
    char data;
    struct LinkNode* next;
}LinkNode;

//栈结构体
typedef struct LinkList {
    LinkNode* head;
    int size;
}LinkStack;

//1，初始化函数
LinkStack* Init_LinkStack() {
    LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    stack->size = 0;
    //头节点，不保存数据信息
    stack->head = (LinkNode*)malloc(sizeof(LinkNode));
    stack->head->data = '\0';
    stack->head->next = NULL;
    return stack;
}
//2，入栈
void Push_LinkStack(LinkStack* stack, char data) {
    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    newNode->data = data;
    newNode->next = stack->head->next;
    stack->head->next = newNode;
    stack->size++;
}
//3，出栈
char Pop_LinkStack(LinkStack* stack) {
    LinkNode* delNode = stack->head->next;
    stack->head->next = delNode->next;
    stack->size--;

    return delNode->data;
}
//4，返回栈顶元素的值
char Top_LinkStack(LinkStack* stack) {
    return stack->head->next->data;
}
//5，返回栈元素的个数
int Size_LinkStack(LinkStack* stack) {
    return stack->size;
}

int isValid(char * s){
    //获得一个栈
    LinkStack* stack = Init_LinkStack();
    //遍历字符串
    for(int i = 0;s[i] != '\0';i++) {
        if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
            Push_LinkStack(stack,s[i]);
            continue;
        }

        if(Size_LinkStack(stack) != 0) {
            if((s[i] == ')' && Top_LinkStack(stack) == '(') ||
               (s[i] == ']' && Top_LinkStack(stack) == '[') ||
               (s[i] == '}' && Top_LinkStack(stack) == '{')
                    ) {
                Pop_LinkStack(stack);
            }else {
                return 0;
            }
        }else {
            return 0;
        }
    }

    if(Size_LinkStack(stack) == 0){
        return 1;
    }else {
        return 0;
    }
}